package jm.algorithm.back_tracking;

/**
 * @Description n皇后问题
 * @date 2022/5/19 14:57
 */
public class Queens {

    public static void main(String[] args) {
        new Queens().placeQueens(4);
    }

    // 索引 = 行号；元素值 = 列号；
    // cols[4] = 5 即第四行第五列
    int[] cols;

    // 统计摆法
    int ways;

    /**
     * n 皇后问题
     * @param n
     */
    void placeQueens(int n){
        if (n < 1) return;
        // 初始化数组值
        cols = new int[n];
        place(0);
        System.out.println(ways);
    }

    /**
     * 从第 row 行开始摆放皇后
     * @param row 行
     */
    void place(int row){
        // 如果上一行摆放成功了，即符合所有摆放条件，最后一行不需要调用。
        if (row == cols.length) {
            show();
            ways++;
            return;
        }

        for (int col = 0; col < cols.length; col++) {
            if (isValid(row,col)){
                // 摆放皇后
                cols[row] = col;
                // 在下一行摆放皇后
                place(row + 1);
                // 回溯
                // 如果将某行的所有可能都摆放完了，会返回到他的上行中，对这行重新摆放，就实现了回溯
            }
        }
    }

    /**
     * 判断 row 行 col 列是否可以摆放，即判断是否需要剪枝
     * @param row
     * @param col
     * @return
     */
    boolean isValid(int row, int col){
        for (int i = 0; i < row; i++) {
            // 判断当前列是否有皇后
            if (cols[i] == col) {
                System.out.println("[" + row + "][" + col + "] = false");
                return false;
            }
            // 判断斜线是否有皇后
            // 要添加的行号减去当前的行号 与 要添加的列号减去当前的列号的绝对值 相等就存在同一斜线。
            // 即斜率  x = y
            if (row - i == Math.abs(col - cols[i])) return false;
        }
        System.out.println("[" + row + "][" + col + "] = true");
        return true;
    }

    /**
     * 打印摆法，有 1，无 0
     */
    void show(){
        for (int row = 0; row < cols.length; row++) {
            for (int col = 0; col < cols.length; col++) {
                if (cols[row] == col){
                    System.out.print("1 ");
                }else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("-------------------");
    }
}
